package com.leetcode.根据算法进行分类.滑动窗口相关;

import java.util.HashMap;

/**
 * @author: ZhouBert
 * @date: 2021/2/23
 * @description: 904. 水果成篮
 * https://leetcode-cn.com/problems/fruit-into-baskets/
 */
public class B_904_水果成篮 {

	public static void main(String[] args) {
		B_904_水果成篮 action = new B_904_水果成篮();
//		test1(action);
//		test2(action);
//		test3(action);
		test4(action);
	}


	public static void test1(B_904_水果成篮 action) {
		// 3
		int[] tree = new int[]{0, 1, 2, 2};
		int res = action.totalFruit(tree);
		System.out.println("res = " + res);
	}

	public static void test2(B_904_水果成篮 action) {
		// 4
		int[] tree = new int[]{1, 2, 3, 2, 2};
		int res = action.totalFruit(tree);
		System.out.println("res = " + res);
	}

	public static void test3(B_904_水果成篮 action) {
		// 5
		int[] tree = new int[]{3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};
		int res = action.totalFruit(tree);
		System.out.println("res = " + res);
	}

	public static void test4(B_904_水果成篮 action) {
		// 4
		int[] tree = new int[]{3, 3, 3, 1, 4};
		int res = action.totalFruit(tree);
		System.out.println("res = " + res);
	}

	/**
	 * 题意理解有点麻烦。大意我是理解了：
	 * 求在子数组中，值只有两个，该子数组的最大长度。
	 * --
	 * 使用 hashMap 统计子数组中元素对应的数量
	 *
	 * @param tree
	 * @return
	 */
	public int totalFruit(int[] tree) {
		int len = tree.length;
		if (len < 3) {
			return len;
		}
		HashMap<Integer, Integer> map = new HashMap<>();
		int left = 0, right = 1;
		map.put(tree[left], 1);
		int num = 1;
		if (map.containsKey(tree[right])) {
			map.put(tree[right], 2);
		} else {
			map.put(tree[right], 1);
			num = 2;
		}
		right++;
		int res = right - left;
		while (right < len) {
			if (!map.containsKey(tree[right]) || map.get(tree[right]) == 0) {
				//说明是新的元素
				map.put(tree[right], 1);
				if (num == 2) {
					//此时已经达到 2 个篮子的限制
					int value = 0;
					do {
						value = map.get(tree[left]) - 1;
						map.put(tree[left], value);
						left++;
					} while (value > 0);
				} else {
					num++;
					res = Math.max(right - left+1, res);
				}
				right++;
			} else {
				//说明是老朋友了
				map.put(tree[right], map.get(tree[right]) + 1);
				right++;
				res = Math.max(right - left, res);
			}
		}

		return res;
	}
}
